package com.xmg.lru;

import java.util.HashMap;
import java.util.Map;

public class MyLRUDemo {

    class Node<K,V>{
        Node<K,V> prev;
        Node<K,V> next;
        K key;
        V value;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            prev = next = null;
        }

        public Node(){
            this.prev = this.next = null;
        }
    }

    class DoubleLinked<K,V>{
        Node<K,V> head;
        Node<K,V> tail;
        public DoubleLinked(){
            head = new Node<>();
            tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }

        public void addHead(Node node){
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        public Node getLast(){
            return tail.prev;
        }

        public void remove(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
        }
    }

    private int cap;
    private HashMap<Integer,Node<Integer,Integer>> map;
    private DoubleLinked<Integer,Integer> list;

    public MyLRUDemo(int cap){
        this.cap = cap;
        map = new HashMap<>();
        list = new DoubleLinked<>();
    }

    public int get(Integer key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node<Integer,Integer> node = map.get(key);
        list.remove(node);
        list.addHead(node);
        return node.value;
    }

    public void put(int key,int value){
        if(map.containsKey(key)){
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key,node);
            list.remove(node);
            list.addHead(node);
        }else{
            Node<Integer, Integer> newNode = new Node<>(key, value);
            if(map.size()<cap){
                map.put(key,newNode);
                list.addHead(newNode);
            }else{
                Node<Integer,Integer> last = list.getLast();
                map.remove(last.key);
                list.remove(last);

                map.put(key,newNode);
                list.addHead(newNode);
            }
        }
    }


    public static void main(String[] args) {
        MyLRUDemo lru = new MyLRUDemo(3);
        lru.put(1,2);
        lru.put(2,3);
        lru.put(3,4);
        System.out.println(lru.map.keySet());
        lru.get(1);

        lru.put(4,5);
        System.out.println(lru.map.keySet());
    }
}
